#include <stdio.h>
#include <stdlib.h>

typedef struct ArrayQueue
{
    int size;     // 队列长度  新的入队的索引 rear = front + size
    int capacity; // 队列容量
    int front;    // 队列头           队尾的索引 rear - 1
    int *data;    // 队列数据
} ArrayQueue_t, *ArrayQueue_p;

ArrayQueue_p ArrayQueueInit(int capacity)
{
    ArrayQueue_p queue = (ArrayQueue_p)malloc(sizeof(ArrayQueue_t));
    queue->capacity = capacity;
    queue->size = 0;
    queue->front = 0;
    queue->data = (int *)malloc(sizeof(int) * capacity);
}

void expand(ArrayQueue_p queue)
{
    queue->capacity *= 2;
    int *new_data = (int *)realloc(queue->data, sizeof(int) * queue->capacity);
    // for (int i = 0; i < queue->size; i++)
    // {
    //     new_data[i] = queue->data[(queue->front + i) % queue->capacity];
    // }
    if (new_data == NULL)
    {
        printf("内存分配失败\n");
        return;
    }
    queue->data = new_data;
}

// 入队
void enQueue(ArrayQueue_p queue, int value)
{
    if (queue->size == queue->capacity)
    {
        printf("队列已满\n");
        expand(queue);
    }
    queue->data[(queue->front + queue->size) % queue->capacity] = value;
    queue->size++;
    printf("入队元素：%d\n", value);
}

// 出队
int deQueue(ArrayQueue_p queue)
{
    if (queue->size == 0)
    {
        printf("队列为空\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->data[queue->front] = 0;
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    printf("出队元素：%d\n", value);
    return value;
}

void traverse(ArrayQueue_p queue)
{
    for (int i = 0; i < queue->size; i++)
    {
        printf("%d ", queue->data[(queue->front + i) % queue->capacity]);
    }
    printf("\n");
}

int main()
{
    ArrayQueue_p q1 = ArrayQueueInit(5);
    enQueue(q1, 11);
    enQueue(q1, 22);
    enQueue(q1, 33);
    enQueue(q1, 44);
    enQueue(q1, 55);
    enQueue(q1, 66);
    enQueue(q1, 77);
    enQueue(q1, 88);
    enQueue(q1, 99);
    enQueue(q1, 100);
    enQueue(q1, 111);
    deQueue(q1);
    traverse(q1);

    return 0;
}